package com.my.collection.graph.v3;

import com.my.collection.graph.v1.ElementExistException;
import com.my.collection.graph.v1.ElementNotFoundException;

import java.util.*;

/**
 * Created by ZhongGang
 * at 2018/10/23 12:46
 * <p>
 * 有向加权图
 */
public class Graph<V> {
    private Map<V, Set<Edge<V>>> table = new HashMap<>();

    /**
     * 添加顶点
     *
     * @param v
     */
    public void addVertex(V v) {
        if (this.table.containsKey(v)) {
            throw new ElementExistException();
        }

        this.table.put(v, new HashSet<>());
    }

    /**
     * 添加顶点间的边
     *
     * @param from
     * @param to
     * @param weight
     */
    public void addEdge(V from, V to, int weight) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        Edge<V> edge = new Edge<>(from, to, weight);
        this.table.get(from).add(edge);
    }

    /**
     * 给定顶点的总权重，顶点间没有边则抛出异常NoSuchRouteException
     *
     * @param vs
     * @return
     */
    public int distance(V... vs) {
        int weight = 0;
        for (int i = 0; i < vs.length - 1; i++) {
            V from = vs[i];
            V to = vs[i + 1];
            Set<Edge<V>> edges = this.table.get(from);
            boolean found = false;
            for (Edge<V> edge : edges) {
                if (Objects.equals(edge.to, to)) {
                    found = true;
                    weight += edge.weight;
                }
            }

            if (!found) {
                throw new NoSuchRouteException();
            }
        }

        return weight;
    }

    /**
     * 两个给定顶点间的所有连通的路径
     *
     * @param from
     * @param to
     * @return
     */
    public List<List<V>> paths(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        List<List<V>> paths = new ArrayList<>();
        java.util.Stack<V> stack = new java.util.Stack<>();
        stack.push(from);
        Map<V, Set<Edge<V>>> visitedEdges = new HashMap<>();
        while (!stack.isEmpty()) {
            V peek = stack.peek();

            if (!visitedEdges.containsKey(peek)) {
                visitedEdges.put(peek, new HashSet<>());
            }

            Set<Edge<V>> edges = this.table.get(peek);
            if (visitedEdges.get(peek).containsAll(edges)) {
                V pop = stack.pop();
                visitedEdges.remove(pop);
            } else {
                for (Edge<V> edge : edges) {
                    if (!visitedEdges.get(peek).contains(edge)) {
                        stack.push(edge.to);
                        visitedEdges.get(peek).add(edge);

                        if (Objects.equals(edge.to, to)) {
                            paths.add(new ArrayList<>(stack));
                            stack.pop();
                        }

                        break;
                    }
                }
            }
        }
        return paths;
    }

    private static class Edge<V> {
        V from;
        V to;
        int weight;

        Edge(V from, V to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<?> edge = (Edge<?>) o;
            return Objects.equals(from, edge.from) &&
                    Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }
    }

}
